import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//力扣322. 零钱兑换
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        int n = coins.length;
        //i是当前i这个数，dp[i]则是当前这个数所用 硬币 最少的个数
        for(int i=1;i<=amount;i++){
            for(int j=0;j<n;j++){
                //coins[j]>i不可能可以组成总金额
                //如果 dp[i - coins[j]] 是 Integer.MAX_VALUE，dp[i - coins[j]] + 1 会变成 Integer.MIN_VALUE。
                if(coins[j]>i||dp[i-coins[j]]==Integer.MAX_VALUE){
                    continue;
                }
                //dp[i-coins[j]]+1表示一个coins[j]硬币加上 i-coins[j] 这个数所用 硬币 最少的个数
                dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}



//力扣139. 单词拆分
class Solution1 {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;

        //还是用暴力+hashSet
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                //看当前 0到j 组成的字符串是否为true，再判断j到i组成的字符串是否存在于字典
                //都成立即 0到i 组成的字符串可以用字典组成，即为true
                if(dp[j]&&wordSet.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        //最后返回依旧是dp[n]
        return dp[n];
    }
}